package com.ztom.offer.v2;

/**
 * 剪绳子 2
 * <p>
 * https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
 *
 * @author ZhangTao
 */
public class Code13CuttingRope {

    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }

        //最大int 2147483647，为防止在某一次 mul乘3已经溢出，类型需要设为long
        long mul = 1;

        //3,3,3,3,3,4
        //3,3,3,3,3,3
        //3,3,3,3,3,2
        //3,3,3,3,3,1  X 此种情况算在和前面 3+1 和为 4
        while (n > 4) {
            //每次乘积后取余防止大数
            mul = mul * 3 % 1000000007;

            n -= 3;
        }
        return (int) (mul * n % 1000000007);
    }
}
